1. Field of the Invention
The present application relates generally to navigation systems.
2. Description of Related Art
With the advent of portable electronic devices, navigation systems are now more commonplace with many users worldwide. Portable electronic devices (“client devices”) such as mobile telephones, PDAs and laptop/palmtop computers may be used while in transit to a specific destination. Navigation servers typically receive requests from a client device for directions to a destination, generate routes by applying routing algorithms to map data, and subsequently provide the route to the client device. Client devices are also capable of storing map data and routing algorithms locally, allowing them to generate routes without the assistance of a navigation server.
The map data generally contains information regarding the locations of streets, connections between streets, and the costs of transitioning between them. The map data may be modeled as a set of data objects (“segments”) connected by links (“arcs”) known as a graph. In a graph data model, each segment represents a street while the arcs represent a transition to the next street. Many popular routing algorithms, such as Dijkstra's algorithm, are designed to operate within the graph model. By using conventional graph theory concepts, routing algorithms attempt to calculate the best route based on metrics (e.g., distance, time, etc.).
After determining a route, navigation servers return the route to the requesting client device, whereupon a map image of the route is then rendered on the client device screen. If a user deviates from the original route, the client device may make an additional route request to the navigation server in order to generate a new route based on the current location. In the event of a network outage, however, the client device might have no access to the map data and routing algorithms on the navigation server.
For systems that download map data, the systems may permit users to regularly download new map data to avoid generating routes based on outdated information.